Nguyễn Hữu Đang (bí danh Phạm Đình Thái) sinh ngày 15 tháng 8 năm 1913 trong một gia đình trí thức tại làng Trà Vi, xã Vũ Công, huyện Kiến Xương, tỉnh Thái Bình.

Ông tham gia Hội Sinh viên thị xã Thái Bình thuộc Thanh niên Cách mạng Đồng chí Hội và bị Pháp bắt vào cuối năm 1930 và bị giam hai tháng rưỡi tại thị xã Thái Bình. Mùa hè năm 1931, Nguyễn Hữu Đang bị đưa ra tòa xét xử, nhưng được tha, vì dưới tuổi thành niên. Sau đó, ông lên Hà Nội theo học Trường Cao đẳng Sư phạm.

Sau khi tốt nghiệp Trường Cao đẳng Sư phạm Hà Nội, Nguyễn Hữu Đang tham gia phong trào Mặt trận Dân chủ Đông Dương (1936-1939) trên lĩnh vực báo chí, viết và làm biên tập viên cho các báo Thời báo, Ngày mới và Tin tức. Ông hoạt động công khai ở Hà Nội, là đồng chí thân thiết của Trường Chinh, Võ Nguyên Giáp, Phạm Văn Đồng, Trần Huy Liệu, Phan Thanh, Nguyễn Văn Tố.

Trong thời kỳ Đảng Cộng sản Đông Dương rút vào hoạt động bí mật (1939-1945), ông hoạt động trong khối trí vận của đảng, chuyên lo việc vận động giới tư sản và trí thức, là một trong những người sáng lập ra Hội Truyền bá Quốc ngữ (do Đảng Cộng sản Đông Dương đứng đằng sau hậu thuẫn) và làm Tổng Thư ký Hội. Năm 1943, ông tham gia Ban chấp hành Hội Văn hóa cứu quốc và gia nhập Tráng đoàn Lam Sơn của tổ chức Hướng đạo sinh Việt Nam. Mùa hè 1944, Nguyễn Hữu Đang tham gia tổ chức và chủ trì Hội nghị Giáo khoa thư Toàn quốc ở Hà Nội. Mùa thu 1944, ông bị bắt và bị giam giữ một tháng tại Nam Định.